
// 1. 二叉树-226-翻转二叉树
// 2. 二叉树-617-合并二叉树
// 3. 二叉树-101-对称二叉树
// 4. 二叉树-104-二叉树的最大深度
// 5. 二叉树-111-二叉树的最小深度
// 6. 二叉树-236-二叉树的最近公共祖先 

// 7. 二叉树-199-二叉树的rightView
// 8. 二叉树-102-层序遍历

// 9. 二叉树-94-二叉树的中序遍历
// 10. 二叉树-98-验证二叉搜索树
// 11. 二叉树-230-二叉搜索树中第k小的元素
// 12. 二叉树-108-将有序数组转为二叉搜索树
// 13. 二叉树-105-从前序与中序遍历序列构造二叉树

// 14. 二叉树-543-二叉树的直径 （深度优先）
// 18. 二叉树-124-二叉树中的最大路径和 （深度优先）
// 17. 二叉树-437-路径总和3

// 15. 二叉树的最大宽度 （广度优先）-----
// 16. 二叉树-114-二叉树转为链表 (先找到左节点的最右节点，根节点的右节点拼在最右，左右对调左变为null， root 变为right的下一个)


// 19. 200-岛屿数量
// 20. 994-腐烂的橘子
// 21. 208-前缀树



// 207-课程表
// 前，中，后，层，深度优先，广度优先， 递归


// 1.翻转二叉树
var invertTree = (root) => {
  if (root === null) return root
  const temp = root.left
  root.left = root.right
  root.right = temp

  invertTree(root.left)
  invertTree(root.right)
  return root
}


// 2.合并二叉树
var mergeTrees = (t1, t2) => {
  if (t1 === null && t2) return t2
  if (t2 === null && t1) return t1
  if (t1 === null && t2 === null) return t1

  t1.val += t2.val

  t1.left = mergeTrees(t1.left, t2.left)
  t1.right = mergeTrees(t1.right, t2.right)
  return t1
}


// 3.对称二叉树
var isSysmetic = (root) => {
  if (root === null) return root;
  isSame(root.left, root.right)
}
var isSame = (left, right) => {
  if (left === null && right === null) return true
  if (left === null || right === null) return false
  return left.val === right.val && isSame(left.left, right.right) && isSame(left.right, right.left)
}

// 4.二叉树的最大深度
var maxDepth = (root) => {
  // let max = 0;
  // if(root === null) return max
  // var dfs = (node, dep) => {
  //     max = Math.max(max, dep)
  //     if(node?.left) dfs(node.left, dep+1)
  //     if(node?.right) dfs(node.right, dep+1)
  // }

  // dfs(root, max)
  // return max + 1

  if(root === null) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

// 5.二叉树的最小深度
var findMinDeep = (root) => {
  if (!root) return 0;
  if (!root.left && !root.right) return 1
  if (!root.left) return findMinDeep(root.right) + 1
  if (!root.right) return findMinDeep(root.left) + 1
  return  Math.min(findMinDeep(root.left), findMinDeep(root.right)) + 1
}

// 6.二叉树的最近公共祖先（后续遍历）
// 前提不会存在重复
var lowestCommonAncestor = (root, p, q) => {
  if (root === null || root === p || root === q) return root
  let left = lowestCommonAncestor(root.left, p, q)
  let right = lowestCommonAncestor(root.right, p, q)
  // 如果在某一个节点，左右都能找到p，q， 将结果一直抛出
  if (left !== null && right !== null) return root
  if (left == null) return right // 向上抛
  return left // 向上传
}


// 7.二叉树的rightview (层序遍历)
var rightview = (root) => {
  if (!root) return [];
  let queue = [root]
  let res = [];

  while (queue.length > 0) {
    let len = queue.length;
    while (len) {
      let node = queue.shift()
      if (len === 1) res.push(node.val)
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
      len--
    }
  }
}

// 8.二叉树的层序遍历 （层序遍历）
var levelOrder = (root) => {
  let queue = [root];
    let res = [];
    if(!root) return [];
    while(queue.length > 0){
        let len = queue.length;
        curLevel = []
        while(len){
            let node = queue.shift();
            curLevel.push(node.val);
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
            len--
        }
        res.push(curLevel)
    }
    return res
}

// 9.二叉树的中序遍历
const inorderTraversal = (root) => {
  let res = []
  var inorder = (node) => {
      if(node === null) return
      inorder(node.left)
      res.push(node.val)
      inorder(node.right)
  }

  inorder(root)
  return res
}

// 10.验证二叉搜索树（中序遍历看）
// 二叉搜索树的特点 右边大于mid 左边的小于mid 整个树都符合 中叙遍历会使数组有序
// 
var isValidBST = function(root) {

  let  arr = [];
  const buildArray = (root) => {
      if(!root) return null
      buildArray(root.left)
      arr.push(root.val)
      buildArray(root.right)
  }
  buildArray(root)
  // 判断是否单调递增
  for(let i = 1; i< arr.length; i++){
      if(arr[i] <= arr[i-1]) {
          return false
      }
  }
  return true

};

// 11.二叉搜索树的第k个最小（中序遍历）
// 利用二叉搜索树的特性
var kthSmallest = function(root, k) {
  let arr = []

  var buildArr = (root) => {
      if(!root) return;
      buildArr(root.left)
      arr.push(root.val);
      buildArr(root.right);
  }
  buildArr(root);
  return arr[k -1]

};


// 12.将有序数组变为二叉搜索树-有点类似二分
var sortedArrayToBST = function(nums) {
  var buildTree = (arr, left, right) => {
      if(left> right) return null;

      let mid = Math.floor(left + (right-left)/2)

      let root = new TreeNode(arr[mid])
      root.left = buildTree(arr, left, mid-1) // 不包含中间
      root.right = buildTree(arr, mid+1, right);

      return root
  }

  return buildTree(nums, 0, nums.length -1)
};


// 13.前中序遍历构造二叉树
var buildTree = function(preorder, inorder) {
  // p: 中左右 i 左中右
  if(inorder.length === 0) return null;// 中序为0， 则没有中间
  const root = new TreeNode(preorder[0])
  const mid = inorder.indexOf(preorder[0])
  root.left = buildTree(preorder.slice(1, mid+1), inorder.slice(0, mid))
  root.right = buildTree(preorder.slice(mid+1), inorder.slice(mid+1))

  return root
};


// 14.二叉树的直径  (深度优先)
// 左右结点拉成一条直线最长
var diameterOfBinaryTree = function(root) {
  let max = 0
  var dfs = (root) => {
      if(!root) return null;
      let left = dfs(root.left)
      let right = dfs(root.right)
      max = Math.max(max, left+right+1-1) // 左深度+右深度 + 自己 -1（求的是步数）
      return Math.max(left, right) + 1; // 以该结点为根结点的最大深度 （加上自己）
  }
  dfs(root)
  return max

};

// 15.二叉树的最大宽度 （广度优先）
var bfs = () => {

}


// 16.二叉搜索树变为链表
var flatten = function(root) {
  while(root){
      if(!root.left) {
          root = root.right
      } else{
          // 处理右结点
          temp = root.left
          while(temp.right) temp = temp.right; // 找到左结点的最右结点
          temp.right = root.right; // 将根结点的最右侧全挂 temp 右结点上

          // 转换完成处理根结点
          root.right = root.left;
          root.left = null;

          root = root.right
      }
  }
};

// 17.路径总和3 dfs 前序
var pathSum = function(root, targetSum) {

  var dfs = (node, sum) => {
      let res = 0;
      if(!node) return 0
      if(node.val === sum){
          res++
      }

      res += dfs(node.left, sum - node.val)
      res += dfs(node.right, sum - node.val)
      return res
  }

  let res = 0;
  if(!root) return res;
  res = dfs(root, targetSum)

  // 一般到上面就结束了但是，他可以以任何结点为根结点
  res += pathSum(root.left, targetSum)
  res += pathSum(root.right, targetSum)

  return res

};

// 18.二叉树的最大路径和
var maxPathSum = function(root) {

  let maxSum = Number.MIN_SAFE_INTEGER

  var dfs = (root) => {
      if(!root) return 0
      const left = dfs(root.left)
      const right = dfs(root.right)

      const innerMaxSum = left + root.val + right
      maxSum = Math.max(maxSum, innerMaxSum)  // 以自身为头结点计算的最大和

      const outputMaxSum = root.val + Math.max(0, left, right) // 当前值加左或则右给出最大值return

      return outputMaxSum < 0 ? 0: outputMaxSum
  }

  dfs(root)
  return maxSum

};

// 19.岛屿数量 - dfs
var numIslands = function(grid) {
  let count = 0;
  for(let i = 0; i< grid.length; i++){
      for(let j = 0; j < grid[0].length; j++){
          if(grid[i][j] === '1'){
              count++
              turnZero(i,j, grid)
          }
      }
  }
  return count
};

var turnZero =(i,j, grid) =>{
  if(i<0 || i>= grid.length || j < 0 || j>= grid[0].length || grid[i][j] === '0') return
  grid[i][j] = '0';
  turnZero(i,j+1, grid)
  turnZero(i,j-1, grid)
  turnZero(i-1, j, grid)
  turnZero(i+1, j, grid)
}


// 20.腐烂的橘子
var orangesRotting = function(grid) {
  let num = 0;
  let temp = [];
  for(let x=0; x< grid.length; x++){
      for(let y = 0; y < grid[0].length; y++){
         grid[x][y] === 2 && temp.push([x,y, num])
      }
  } 
  console.log(temp)
  while(temp.length){
      const [x,y,n] = temp.shift();  // 这是shift 也很重要
      num = n
      console.log(n)
      let ways = [[x, y-1],[x, y+1], [x-1,y],[x+1,y]]
      for(let i = 0; i< ways.length; i++){
          let r = ways[i][0]
          let c = ways[i][1]
          if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] !== 1) continue  // 层序遍历 continue
          grid[r][c] = 2;
          temp.push([r,c, num+1])
      }
  }

  // 寻找步关联的部分
  for(let x=0; x< grid.length; x++){
      for(let y = 0; y < grid[0].length; y++){
         grid[x][y] === 1 && (num = -1)
      }
  } 
  return num
};

console.log(orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))



// 21.前缀树 a.b.c.d 插入的时候如果是单词带一个isword tag
var Trie = function() {
  this.root = Object.create(null)
  this.traverse = (word) => {
      let node = this.root;
      for(const c of word){
          node = node[c]
          if(!node) return null
      }
      return node
  }
};
Trie.prototype.insert = function(word) {
  let node = this.root;
  for(const c of word){
      if(!node[c]) node[c] = Object.create(null)
      node = node[c]
  }
  node.isWord = true // 标记是否是完整的单词

};
Trie.prototype.search = function(word) {
  const node = this.traverse(word)
  return !!node && !!node.isWord // 区别startwith 必须是单词结束
};
Trie.prototype.startsWith = function(prefix) {
  return !!this.traverse(prefix)
};
